package main

import (
	"container/list"
)

type state_node_next_type = map[rune]uint32

type state_node_type struct {
	End         bool
	Level       uint32
	FailIndex   uint32
	ParentIndex uint32
	Next        state_node_next_type
}

type state_pair_type struct {
	r rune
	i uint32
}

type ACAutomaton struct {
	TireTree []state_node_type
}

func (this *ACAutomaton) BuildACFSM(patterns []string) {
	this.BuildGoto(patterns)
	this.BuildFail()
}

func (this *ACAutomaton) BuildGoto(patterns []string) {
	state := state_node_type{
		End:         false,
		Level:       0,
		FailIndex:   0,
		ParentIndex: 0,
	}
	this.TireTree = append(this.TireTree, state)

	var index uint32
	for _, pattern := range patterns {
		index = 0
		for _, r := range pattern {
			if this.TireTree[index].Next != nil {
				if v, ok := this.TireTree[index].Next[r]; ok {
					index = v
					continue
				}
			} else {
				this.TireTree[index].Next = make(state_node_next_type)
			}
			state.ParentIndex = index
			state.Level = this.TireTree[index].Level + 1
			this.TireTree = append(this.TireTree, state)
			this.TireTree[index].Next[r] = uint32(len(this.TireTree) - 1)
			index = uint32(len(this.TireTree) - 1)
		}
		this.TireTree[index].End = true
	}
}

func (this *ACAutomaton) BuildFail() {
	if len(this.TireTree) == 0 {
		return
	}

	l := list.New()

	var findex uint32
	this.TireTree[0].FailIndex = 0
	for r, i := range this.TireTree[0].Next {
		this.TireTree[i].FailIndex = 0
		l.PushBack(&state_pair_type{r, i})
	}

	for l.Len() > 0 {
		pair := l.Remove(l.Front()).(*state_pair_type)

		if this.TireTree[pair.i].Next != nil {
			for r, i := range this.TireTree[pair.i].Next {
				l.PushBack(&state_pair_type{r, i})
			}
		}

		if this.TireTree[pair.i].ParentIndex == 0 {
			continue
		}

		findex = this.TireTree[this.TireTree[pair.i].ParentIndex].FailIndex
		for {
			if this.TireTree[findex].Next != nil {
				if v, ok := this.TireTree[findex].Next[pair.r]; ok {
					this.TireTree[pair.i].FailIndex = v
				}

				if findex == 0 {
					break
				}
			}
			findex = this.TireTree[findex].FailIndex
		}
	}
}

func (this *ACAutomaton) Replace(s string, r rune) string {
	if len(this.TireTree) < 2 {
		return s
	}

	rs := []rune(s)

	var index uint32
	n := uint32(len(rs))
	for i := uint32(0); i < n; {
		if this.TireTree[index].Next != nil {
			if v, ok := this.TireTree[index].Next[rs[i]]; ok {
				index = v
			} else {
				if index == 0 {
					i++
				}
				index = this.TireTree[index].FailIndex
				continue
			}
		} else {
			if index == 0 {
				i++
			}
			index = this.TireTree[index].FailIndex
			continue
		}

		if this.TireTree[index].End {
			for j := uint32(0); j < this.TireTree[index].Level; j++ {
				rs[i-j] = r
			}
		}
		i++
	}

	return string(rs)
}

func (this *ACAutomaton) Contain(s string) bool {
	if len(this.TireTree) < 2 {
		return false
	}

	rs := []rune(s)

	var index uint32
	n := uint32(len(rs))
	for i := uint32(0); i < n; {
		if this.TireTree[index].Next != nil {
			if v, ok := this.TireTree[index].Next[rs[i]]; ok {
				index = v
			} else {
				if index == 0 {
					i++
				}
				index = this.TireTree[index].FailIndex
				continue
			}
		} else {
			if index == 0 {
				i++
			}
			index = this.TireTree[index].FailIndex
			continue
		}

		if this.TireTree[index].End {
			return true
		}
		i++
	}

	return false
}
